package graph.matchProblem;
/**
 * 
 * @Title: BipartiteMatching.java 
 * @Package graph.matchProblem 
 * @Description: 使用最大流算法解决二分图的最大匹配问题
 * @author CandyWall   
 * @date 2021年1月23日 下午12:53:06 
 * @version V1.0
 */

import java.util.ArrayList;
import java.util.Arrays;

import graph.unweighted.CandyGraph;
import graph.unweighted.dfs.biPartitionDetection.CandyBiPartitionDetection;
import graph.weighted.CandyWeightedGraph;
import graph.weighted.maxFlow.CandyMaxFlow;
/**
 * 
 * @Title: CandyBipartiteMatching.java 
 * @Package graph.matchProblem 
 * @Description: 最大流算法求解匹配问题
 * @author CandyWall   
 * @date 2021年1月23日 下午5:07:54 
 * @version V1.0
 */
public class CandyBipartiteMatching {
    private CandyGraph graph;
    private int maxMatching;
    public CandyBipartiteMatching(CandyGraph graph) {
        if(graph.isDirected()) {
            throw new IllegalArgumentException("二分图匹配问题只能处理无权图！");
        }
        CandyBiPartitionDetection biPartitionDetection = new CandyBiPartitionDetection(graph);
        if(!biPartitionDetection.isBiPartitionGraph()) {
            throw new IllegalArgumentException("当前图不是二分图！");
        }
        this.graph = graph;
        // 创建网络流模型，包含源点和汇点的有向图
        CandyWeightedGraph weightedGraph = new CandyWeightedGraph(graph.getVertex_num() + 2, true);
        ArrayList<Integer>[] biParts = biPartitionDetection.getBiParts();
        // 源点指向二分图中的第一部分的元素
        for(int w : biParts[0]) {
            weightedGraph.addEdge(graph.getVertex_num(), w, 1);
        }
        // 二分图中的另一部分元素指向汇点
        for(int w : biParts[1]) {
            weightedGraph.addEdge(w, graph.getVertex_num() + 1, 1);
        }
        // 遍历第一部分和第二部分中的元素，如果在无向图中有边，
        // 就将第一部分中的元素指向第二部分中的元素
        for(int v : biParts[0]) {
            for(int w : biParts[1]) {
                if(graph.hasEdge(v, w)) {
                    weightedGraph.addEdge(v, w, 1);
                }
            }
        }
        // 求解最大流，即最大匹配
        CandyMaxFlow maxFlow = new CandyMaxFlow(weightedGraph, graph.getVertex_num(), graph.getVertex_num() + 1);
        maxMatching = maxFlow.getMaxFlow();
    }
    
    /**
     * 获取最大匹配数
     * @return
     */
    public int getMaxMatching() {
        return maxMatching;
    }
    
    /**
     * 获取完美匹配数
     * @return
     */
    public boolean isPerfectMatching() {
        return maxMatching * 2 == graph.getVertex_num();
    }

    public static void main(String[] args) {
        CandyGraph graph1 = new CandyGraph("testData/matchProblem/graph1.txt");
        CandyBipartiteMatching bipartiteMatching1 = new CandyBipartiteMatching(graph1);
        System.out.println("最大匹配数：" + bipartiteMatching1.getMaxMatching() + "，是否是完美匹配：" + bipartiteMatching1.isPerfectMatching());
        CandyGraph graph2 = new CandyGraph("testData/matchProblem/graph2.txt");
        CandyBipartiteMatching bipartiteMatching2 = new CandyBipartiteMatching(graph2);
        System.out.println("最大匹配数：" + bipartiteMatching2.getMaxMatching() + "，是否是完美匹配：" + bipartiteMatching2.isPerfectMatching());
        CandyGraph graph3 = new CandyGraph("testData/matchProblem/graph3.txt");
        CandyBipartiteMatching bipartiteMatching3 = new CandyBipartiteMatching(graph3);
        System.out.println("最大匹配数：" + bipartiteMatching3.getMaxMatching() + "，是否是完美匹配：" + bipartiteMatching3.isPerfectMatching());
        CandyGraph graph4 = new CandyGraph("testData/matchProblem/graph4.txt");
        CandyBipartiteMatching bipartiteMatching4 = new CandyBipartiteMatching(graph4);
        System.out.println("最大匹配数：" + bipartiteMatching4.getMaxMatching() + "，是否是完美匹配：" + bipartiteMatching4.isPerfectMatching());
    }
}
